package com.lw.leetcode.back.c;

import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 1301. 最大得分的路径数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/16 10:09
 */
public class PathsWithMaxScore {

    public static void main(String[] args) {
        PathsWithMaxScore test = new PathsWithMaxScore();

        // [7,1]
//        List<String> list = Arrays.asList("E23", "2X2", "12S");

        // [4,2]
        List<String> list = Arrays.asList("E12", "1X1", "21S");

        // [0,0]
//        List<String> list = Arrays.asList("E11", "XXX", "11S");

        // [0，1]
//        List<String> list = Arrays.asList("EX", "XS");

        int[] ints = test.pathsWithMaxScore(list);
        System.out.println(Arrays.toString(ints));
    }

    public int[] pathsWithMaxScore(List<String> board) {

        int size = board.size();
        int l = size - 1;
        int[][] arr = new int[size][size];
        arr[l][l] = board.get(l).charAt(l) - '0';
        for (int i = l; i >= 0; i--) {
            for (int j = l; j >= 0; j--) {
                if (i == l && j == l) {
                    continue;
                }
                char c = board.get(i).charAt(j);
                if (c == 'X') {
                    arr[i][j] = -1;
                    continue;
                }

                int a1 = check(l, i + 1, j, arr);
                int a2 = check(l, i, j + 1, arr);
                int a3 = check(l, i + 1, j + 1, arr);
                a3 = Math.max(a1, Math.max(a2, a3));
                if (a3 == -1) {
                    arr[i][j] = -1;
                } else {
                    arr[i][j] = a3 + c - '0';
                }
            }
        }
        if (arr[0][0] == -1) {
            return new int[]{0, 0};
        }
        int i = arr[0][0] - 'S' - 'E' + '0' + '0';
        int j = find(board, i);
        return new int[]{i, j};
    }


    private int check(int l, int i, int j, int[][] arr) {
        l++;
        if (i == l || j == l) {
            return -1;
        }
        return arr[i][j];
    }

    private int check2(int l, int i, int j, int[][] arr) {
        l++;
        if (i == l || j == l || arr[i][j] == -1) {
            return Integer.MAX_VALUE;
        }
        return arr[i][j];
    }

    private int find(List<String> board, int value) {

        int size = board.size();
        int l = size - 1;
        int[][] arr = new int[size][size];
        long[][] counts = new long[size][size];

        arr[l][l] = value;
        counts[l][l] = 1;
        for (int i = l; i >= 0; i--) {
            for (int j = l; j >= 0; j--) {
                if (i == l && j == l) {
                    continue;
                }
                char c = board.get(i).charAt(j);
                if (c == 'X') {
                    arr[i][j] = -1;
                    continue;
                }
                int a1 = check2(l, i + 1, j, arr);
                int a2 = check2(l, i, j + 1, arr);
                int a3 = check2(l, i + 1, j + 1, arr);
                int a = Math.min(a1, Math.min(a2, a3));
                if (a == Integer.MAX_VALUE) {
                    arr[i][j] = -1;
                } else {
                    arr[i][j] = a - c + '0';
                    long count = 0;
                    if (a1 == a) {
                        count += counts[i + 1][j];
                    }
                    if (a2 == a) {
                        count += counts[i][j + 1];
                    }
                    if (a3 == a) {
                        count += counts[i + 1][j + 1];
                    }
                    counts[i][j] = count % 1000000007;
                }
            }
        }
        return (int) counts[0][0];
    }

}
